package algorithmicFoundation.homework.day3;


import java.util.Iterator;
import java.util.NoSuchElementException;

/**
 * deque双端队列
 *
 * @author 86155
 * @date 2025/08/09
 */
public class Deque<Item> implements Iterable<Item> {

    /**
     * 存放数据
     */
    private Item[] items;

    /**
     * 头指针 第一个有效元素
     */
    private int head;

    /**
     * 尾指针 最后一个有效元素 +1
     */
    private int tail;

    /**
     * 容量
     */
    private final int DEFAULT_CAPACITY  = 10;

    /**
     * 记录数量
     */
    private int size;

    /**
     * construct an empty deque
     */
    public Deque(){
        //初始化数组
        this.items = (Item[]) new Object[DEFAULT_CAPACITY];
        head = tail = size = 0;
    }

    /**
     * is the deque empty?
     *
     * @return boolean
     */
    public boolean isEmpty(){
        return size == 0;
    }

    /**
     *
     * @return return the number of items on the deque
     */
    public int size(){
        return size;
    }

    /**
     * add the item to the front
     * @param item
     */
    public void addFirst(Item item){
        //校验
        vail(item);
        //增加
        if (head == 0) {
            //需要扩容
            resize(true);
        }
        items[--head] = item;
        size++;
    }

    /**
     * true:需要扩容
     * false: 收缩
     */
    private void resize(boolean isExpansion) {
        int len = this.items.length;
        int newLen = isExpansion ?
                len << 1 :
                Math.max(DEFAULT_CAPACITY, len >>> 1);
        //双倍扩容 //双倍扩容
        Item[] newArray = (Item[]) new Object[newLen];
        // 留出前后空间
        int newHead = newLen / 3;

        System.arraycopy(items,head,newArray,newHead,size);
        //覆盖
        this.items = newArray;
        this.head = newHead;
        this.tail = head + size;
    }

    /**
     * 添加到最后
     * add the item to the back
     * @param item 项目
     */
    public void addLast(Item item){
        vail(item);
        //增加
        if (tail == items.length) {
            //需要扩容
            resize(true);
        }
        items[tail++] = item;
        size++;
    }


    /**
     * 校验item
     *
     * @param item
     */
    private void vail(Item item) {
        if (item == null) {
            throw new IllegalArgumentException("item is null");
        }
    }

    /**
     * remove and return the item from the front
     * @return {@link Item}
     */
    public Item removeFirst(){
        //校验
        vailRemove();
        Item temp = this.items[head];
        this.items[head++] = null;
        //收缩
        size--;
        //数量只有四分之一的时候就收缩数组
        if (size > 0 && size == items.length / 4) {resize(false);}

        return temp;
    }


    /**
     * 删除最后一个
     * remove and return the item from the back
     * @return {@link Item}
     */
    public Item removeLast(){
        //校验
        vailRemove();
        Item temp = this.items[--tail];
        this.items[tail] = null;
        //收缩
        size--;
        //数量只有四分之一的时候就收缩数组
        if (size > 0 && size == items.length / 4) {
            resize(false);
        }
        return temp;
    }

    /**
     * 删除校验
     */
    private void vailRemove() {
        if (isEmpty()) {
            throw new java.util.NoSuchElementException("empty");
        }
    }

    /**
     * 迭代器
     *
     * @return return an iterator over items in order from front to back
     */
    @Override
    public Iterator<Item> iterator() {
        return new Iterator<Item>() {
            private int current = head;
            private final int end = tail;
            private final Item[] snapshot = items.clone(); // 防止扩容影响

            @Override
            public boolean hasNext() {
                return current < end;
            }

            @Override
            public Item next() {
                if (!hasNext()) {throw new NoSuchElementException();}
                return snapshot[current++];
            }
        };
    }

    // unit testing (required)
    public static void main(String[] args){
        Deque<Integer> de = new Deque<>();
        de.addFirst(1);
        de.addFirst(2);
        de.addFirst(3);
        de.addFirst(4);
        de.size();
        de.addLast(1);
        de.addLast(2);
        de.addLast(3);
        de.addLast(4);
        de.size();
        de.removeFirst();
        de.size();
        de.removeLast();
        de.size();
        for (int a : de) {
            System.out.println(a);
        }
    }

}